/*************************************************************************
  > File Name: 1_fib_step.c
  > Author: IvanLxy
  > Mail: yoyiyyo@163.com 
  > Created Time: Wed 18 Mar 2020 05:12:53 AM PDT
************************************************************************/
/*要走完n级，每次跨1~2个，有多少种方法*/
/*要走上n级台阶，必然是从n − 1级台阶迈一步或者是从n − 2级台阶迈两步*/
/*所以到达n级台阶就要到达n − 1级台阶的方法数加上到达n − 2级台阶的方法数之和*/
#include <stdio.h>
#define N 20

int g_total_recursion = 0;//递归分治执行次数
int g_total_dynamic = 0;  //动态规划法执行次数

int step1(int n)
{
    g_total_recursion++;
    if(n == 1 || n == 2 )
    {
        return n;
    }
    return step1(n-1) + step1(n-2);
}
int step(int *dp,int n)
{
    g_total_dynamic++;
    if(n == 1 || n == 2)
    {
        return n;
    }
    
    if(!dp[n - 1])
    {
        dp[n-1] = step(dp,n - 1);
    }

    if(!dp[n - 2])
    {
        dp[n - 2] = step(dp,n - 2);
    }
    return dp[n - 1] + dp[n - 2];
}


int main()
{
    int dp[N + 1] = {0};
    int i;
    for(i = 1; i <= N ; i++)
    {
        printf("%d  |  %d\n",step1(i),step(dp,i));
    }
    printf("total_recursion:%d\n",g_total_recursion);
    printf("total_dynamic  :%d\n",g_total_dynamic);  

    return 0;
}
